package leetcode.editor.cn;
//给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。
// 返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现
//次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums1 = [1,2,2,1], nums2 = [2,2]
//输出：[2,2]
// 
//
// 示例 2: 
//
// 
//输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
//输出：[4,9] 
//
// 
//
// 提示： 
//
// 
// 1 <= nums1.length, nums2.length <= 1000 
// 0 <= nums1[i], nums2[i] <= 1000 
// 
//
// 
//
// 进阶： 
//
// 
// 如果给定的数组已经排好序呢？你将如何优化你的算法？ 
// 如果 nums1 的大小比 nums2 小，哪种方法更优？ 
// 如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？ 
// 
//
// Related Topics 数组 哈希表 双指针 二分查找 排序 👍 1014 👎 0


import java.util.*;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution199 {

    public int[] intersect11(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map1 = new HashMap<>();
        for (int i : nums1) {
            map1.put(i, map1.getOrDefault(i, 0) + 1);
        }
        List<Integer> res = new LinkedList<>();

        if (!map1.isEmpty()) {
            for (int i : nums2) {
                if (map1.containsKey(i) && map1.get(i) > 0) {
                    res.add(i);
                    map1.put(i, map1.get(i) - 1);
                }
            }
        }
        return res.stream().mapToInt(Integer::intValue).toArray();
    }


    public int[] intersect1(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map1 = new HashMap<>();
        Map<Integer, Integer> map2 = new HashMap<>();
        for (int i : nums1) {
            map1.put(i, map1.getOrDefault(i, 0) + 1);
        }
        for (int i : nums2) {
            map2.put(i, map2.getOrDefault(i, 0) + 1);
        }
        List<Integer> res = new LinkedList<>();
        if (!map1.isEmpty()) {
            map1.forEach((key, value) -> {
                if (map2.containsKey(key)) {
                    int n = value < map2.get(key) ? value : map2.get(key);
                    for (int i = 0; i < n; i++) {
                        res.add(key);
                    }
                }
            });
        }
        return res.stream().mapToInt(Integer::intValue).toArray();
    }


    public int[] intersect2(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        List<Integer> res = new LinkedList<>();
        int index1 = 0;
        int index2 = 0;
        while (index1 < nums1.length && index2 < nums2.length) {
            int num1 = nums1[index1];
            int num2 = nums2[index2];
            if (num1 > num2) {
                index2++;
            } else if (num1 < num2) {
                index1++;
            } else {
                res.add(num1);
                index1++;
                index2++;
            }
        }
        return res.stream().mapToInt(Integer::intValue).toArray();
    }


    public int[] intersect(int[] nums1, int[] nums2) {
        //必须先排序
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int i = 0, j = 0, k = 0;
        /**
         * 类似归并排序的双工作指针
         * 1、当两者不同时，小的那个数组前进
         * 2、两者相同的时候，两者同时前进，且记录当前数字
         * 3、当一数组遍历完成时候推出循环（难点，有一个数组遍历完便可以结束循环）
         */
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) {
                i++;
            } else if (nums1[i] > nums2[j]) {
                j++;
            } else {
                nums1[k++] = nums1[i++];
                j++;
            }
        }
        return Arrays.copyOfRange(nums1, 0, k);
    }

}
//leetcode submit region end(Prohibit modification and deletion)
